Internet Surfer 2.0

home *** CD-ROM | disk | FTP | other *** search

/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / textfile / faqs / puzz_faq / part14 < prev next >

Wrap

Internet Message Format | 1992-12-26 | 59.4 KB

Xref: bloom-picayune.mit.edu rec.puzzles:18151 news.answers:3082 Newsgroups: rec.puzzles,news.answers Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!sol.ctr.columbia.edu!destroyer!uunet!questrel!chris From: uunet!questrel!chris (Chris Cole) Subject: rec.puzzles FAQ, part 14 of 15 Message-ID: <puzzles-faq-14_717034101@questrel.com> Followup-To: rec.puzzles Summary: This posting contains a list of Frequently Asked Questions (and their answers). It should be read by anyone who wishes to post to the rec.puzzles newsgroup. Sender: chris@questrel.com (Chris Cole) Reply-To: uunet!questrel!faql-comment Organization: Questrel, Inc. References: <puzzles-faq-1_717034101@questrel.com> Date: Mon, 21 Sep 1992 00:09:53 GMT Approved: news-answers-request@MIT.Edu Expires: Sat, 3 Apr 1993 00:08:21 GMT Lines: 1574 Archive-name: puzzles-faq/part14 Last-modified: 1992/09/20 Version: 3 ==> logic/verger.s <== The puzzler tried to take the test; Intriguing rhymes he wished to best. But "Fifty and ten dozens twenty" made his headache pound aplenty. When he finally found some leisure, He took to task this witty treasure. "The product of the age must be Twenty-Four Hundred Fifty!" Knowing that, he took its primes, permuted them as many times as needed, til he found amounts equal to, by all accounts, twice the Verger's age, so that He would have that next day's spat. The reason for the lad's confusion was due to multiple solution! Hence he needed one more clue to give the answer back to you! Since only one could fit the bill, and then confirm the priest's age still, the eldest age of each solution by one could differ, with no coercion. <=(Sorry) Else, that last clue's revelation would not have brought information! With two, two, five, seven, and seven, construct three ages, another set of seven. Two sets of three yield sixty-four, Examine them, yet one time more. The eldest age of each would be forty-nine, and then, fifty! With lack of proper rhyme and meter, I've tried to be the first completor of this poem and a puzzle; my poetry, you'd try to muzzle! And lest you think my wit is thrifty, The answer, of course, must be fifty! If dispute, you wish to tender, note my addresss, as the sender! -- Kevin Nechodom <knechod@stacc.med.utah.edu> ==> logic/weighing/balance.p <== You are given N balls and a balance scale and told that one ball is slightly heavier or lighter than the other identical ones. The scale lets you put the same number of balls on each side and observe which side (if either) is heavier. 1. What's the minimum # of weighings X (and way of doing them) that will always find the unique ball and whether it's heavy or light? 2. If you are told the unique ball is, in fact, heavier than the others, what's the minimum # of weighings Y to find it? ==> logic/weighing/balance.s <== Martin Gardner gave a neat solution to this problem. Assume that you are allowed N weighings. Write down the 3^N possible length N strings of the symbols '0', '1', and '2'. Eliminate the three such strings that consist of only one symbol repeated N times. For each string, find the first symbol that is different from the symbol preceeding it. Consider that pair of symbols. If that pair is not 01, 12, or 20, cross out that string. In other words, we only allow strings of the forms 0*01.*, 1*12.*, or 2*20.* ( using ed(1) regular expressions ). You will have (3^N-3)/2 strings left. This is how many balls you can handle in N weighings. Perform N weighings as follows: For weighing I, take all the balls that have a 0 in string position I, and weigh them against all the balls that have a 2 in string position I. If the side with the 0's in position I goes down, write down a 0. If the other side goes down, write down a 2. Otherwise, write down a 1. After the N weighings, you have written down an N symbol string. If your string matches the string on one of the balls, then that is the odd ball, and it is heavy. If none of them match, than change every 2 to a 0 in your string, and every 0 to a 2. You will then have a string that matches one of the balls, and that ball is lighter than the others. Note that if you only have to identify the odd ball, but don't have to determine if it is heavy or light, you can handle (3^N-3)/2+1 balls. Label the extra ball with a string of all 1's, and use the above method. Note also that you can handle (3^N-3)/2+1 balls if you *do* have to determine whether it is heavy or light, provided you have a single reference ball available, which you know has the correct weight. You do this by labelling the extra ball with a string of all 2s. This results in it being placed on the same side of the scales each time, and in that side of the scales having one more ball than the other each time. So you put the reference ball on the other side of the scales to the "all 2s" ball on each weighing. Proving that this works is straightforward, once you notice that the method of string construction makes sure that in each position, 1/3 of the strings have 0, 1/3 have 1, and 1/3 have 2, and that if a string occurs, then the string obtained by replacing each 0 with a 2 and each 2 with a 0 does not occur. ==> logic/weighing/box.p <== You have ten boxes; each contains nine balls. The balls in one box weigh 0.9 kg; the rest weigh 1.0 kg. You have one weighing on a scale to find the box containing the light balls. How do you do it? ==> logic/weighing/box.s <== Number the boxes 0-9. Take 0 balls from box 0, 1 ball from box 1, 2 balls from box 2, etc. Now weight all those balls and follow this table: If odd box is Weight is 0 45 kg 1 44.9 kg 2 44.8 kg 3 44.7 kg 4 44.6 kg 5 44.5 kg 6 44.4 kg 7 44.3 kg 8 44.2 kg 9 44.1 kg ==> logic/weighing/gummy.bears.p <== Real gummy drop bears have a mass of 10 grams, while imitation gummy drop bears have a mass of 9 grams. Spike has 7 cartons of gummy drop bears, 4 of which contain real gummy drop bears, the others imitation. Using a scale only once and the minimum number of gummy drop bears, how can Spike determine which cartons contain real gummy drop bears? ==> logic/weighing/gummy.bears.s <== Spike used 51 gummy drop bears: from the 7 boxes he took respectively 0, 1, 2, 4, 7, 13, and 24 bears. The notion is that each box of imitation bears will subtract its number of bears from the total "ideal" weight of 510 grams (1 gram of missing weight per bear), so Spike weighs the bears, subtracts the result from 510 to obtain a number N, and finds the unique combination of 3 numbers from the above list (since there are 3 "imitation" boxes) that sum to N. The trick is for the sums of all triples selected from the set S of numbers of bears to be unique. To accomplish this, I put numbers into S one at a time in ascending order, starting with the obvious choice, 0. (Why is this obvious? If I'd started with k > 0, then I could have improved on the resulting solution by subtracting k from each number) Each new number obviously had to be greater than any previous, because otherwise sums are not unique, but also the sums it made when paired with any previous number had to be distinct from all previous pairs (otherwise when this pair is combined with a third number you can't distinguish it from the other pair)--except for the last box, where we can ignore this point. And most obviously all the new triples had to be distinct from any old triples; it was easy to find what the new triples were by adding the newest number to each old sum of pairs. Now, in case you're curious, the possible weight deficits and their unique decompositions are: 3 = 0 + 1 + 2 5 = 0 + 1 + 4 6 = 0 + 2 + 4 7 = 1 + 2 + 4 8 = 0 + 1 + 7 9 = 0 + 2 + 7 10 = 1 + 2 + 7 11 = 0 + 4 + 7 12 = 1 + 4 + 7 13 = 2 + 4 + 7 14 = 0 + 1 + 13 15 = 0 + 2 + 13 16 = 1 + 2 + 13 17 = 0 + 4 + 13 18 = 1 + 4 + 13 19 = 2 + 4 + 13 20 = 0 + 7 + 13 21 = 1 + 7 + 13 22 = 2 + 7 + 13 24 = 4 + 7 + 13 25 = 0 + 1 + 24 26 = 0 + 2 + 24 27 = 1 + 2 + 24 28 = 0 + 4 + 24 29 = 1 + 4 + 24 30 = 2 + 4 + 24 31 = 0 + 7 + 24 32 = 1 + 7 + 24 33 = 2 + 7 + 24 35 = 4 + 7 + 24 37 = 0 + 13 + 24 38 = 1 + 13 + 24 39 = 2 + 13 + 24 41 = 4 + 13 + 24 44 = 7 + 13 + 24 Note that there had to be (7 choose 3) distinct values; they end up ranging from 3 to 44 inclusive with 7 numbers missing: 4, 23, 34, 36, 40, 42, and 43. -- David Karr (karr@cs.cornell.edu) ==> logic/weighing/weighings.p <== Some of the supervisors of Scandalvania's n mints are producing bogus coins. It would be easy to determine which mints are producing bogus coins but, alas, the only scale in the known world is located in Nastyville, which isn't on very friendly terms with Scandalville. In fact, Nastyville's king will only let you use the scale twice. Your job? You must determine which of the n mints are producing the bogus coins using only two weighings and the minimum number of coins (your king is rather parsimonious, to put it nicely). This is a true scale, i.e. it will tell you the weight of whatever you put on it. Good coins are known to have a weight of 1 ounce and it is also known that all the bogus mints (if any) produce coins that are light or heavy by the same amount. Some examples: if n=1 then we only need 1 coin, if n=2 then clearly 2 coins suffice, one from each mint. What are the solutions for n=3,4,5? What can be said for general n? ==> logic/weighing/weighings.s <== Oh gracious and wise king, I have solved this problem by first simplifying and then expanding. That is, consider the problem of being allowed only a single weighing. Stop reading right now if you want to think about it further. There are three possible outcomes for each mint (light, OK, heavy) which may be represented as (-1, 0, +1). Now, let each mint represent one place in base 3. Thus, the first mint is the ones place, the second the threes place, the third is the nines place and so on. The number of coins from each mint must equal the place. That is, we'll have 1 coin from mint 1, 3 from mint 2, 9 from mint 3, and, in general, 3^(n-1) from mint n. By weighing all coins at once, we will get a value between 1 + 3 + 9 + ... and -1 + -3 + -9 + ... In fact, we notice that that value will be unique for any mint outcomes. Thus, for the one weighing problem, we need sum for i=1 to n (3^(i-1)) which evaluates to (3^n - 1)/2 I'm fairly satisfied that this is a minimum for a single weighing. What does a second weighing give us? Well, we can divide the coins into two groups and use the same method. That is, if we have 5 mints, one weighing will be: 1 coin from mint 1 + 3 coins from mint 2 + 9 coins from mint 3 while the other weighing will be: 1 coin from mint 4 + 3 coins from mint 5 It's pretty plain that this gives us a total coinage of: 3^(n/2) - 1 for even n and, after some arithmetic agitation: 2 * 3^((n-1)/2) - 1 for odd n I think the flaw in this solution is that we don't know ahead of time the amount by which the coins are off weight. So if you weigh 1 coin from mint 1 together with 3 coins from mint 2 and the result is heavy by 3x units, you still don't know whether the bogus coins are from mint 3 (heavy by x units) or from mint 1 (heavy by 3x units). Note that we're not given the error amount, only the fact that is is equal for all bogus coins. Here is my partial solution: After considering the above, it would seem that on each of the two weighings we must include coins from all of the mints (except for the special cases of small n). So let ai (a sub i) be the number of coins from mint i on weighing 1 and bi be the number of coins from mint i on weighing 2. Let the error in the bogus coins have a value x, and let ci be a the counterfeit function: ci is 0 if mint i is good, 1 otherwise. Then Sum ai ci x = delta1 error on weighing 1 Sum bi ci x = delta2 error on weighing 2 Now the ratio of delta1 to delta2 will be rational regardless of the value of x, since x will factor out; let's call this ratio p over q (p and q relatively prime). We would like to choose { ai } and { bi } such that for any set of mints J, which will be a subset of { 1 , 2 , ... , n }, that Sum aj ( = Sum ai ci ) is relatively prime to Sum bj. If this is true then we can determine the error x; it will simply be delta1/p, which is equal to delta2/q. If the { ai } have been carefully chosen, we should be able to figure out the bogus mints from one of the weighings, provided that all subsets ( { { aj } over all J } ) have unique sums. This was the strategy proposed above, where is was suggested that ai = 3 ** (i-1) ; note that you can use base 2 instead of base 3 since all the errors have the same sign. Well, for the time being I'm stumped. This agrees with the analysis I've been fighting with. I actually came up with a pair of functions that "almost" works. So that the rest of you can save some time (in case you think the way I did): Weighing 1: 1 coin from each mint Weighing 2: 2^(k-1) coins from mint k, for 1...k...n (total 2^n - 1 coins) Consider the n mints to be one-bit-each -- bit set -> mint makes bogus coins. Then we can just state that we're trying to discover "K", where K is a number whose bit pattern _just_ describes the bogosity of each mint. OK - now, assuming we know 'x', and we only consider the *difference* of the weighing from what it should be, for weighing 1, the devaiation is just the Hamming weight of K -- that is the number of 1-bits in it -- that is, the number of bogosifying mints. For weighing 2, the deviation is just K! When the nth bit of K is set, then that mint contributes just 2^n to the deviation, and so the total deviation will just be K. So that set me in search of a lemma: given H(x) is the hamming weight of x, is f(x) = x / H(x) a 1-1 map integers into rationals? That is, if x/H(x) = y/H(y) can we conclude that x = y? The answer (weep) is NO. The lowest pair I could find are 402/603 (both give the ratio 100.5). Boy it sure looked like a good conjecture for a while! Sigh. There are two parts to the problem. First let us try to come up with a solution to finding the answer in 2 weighings - then worry about using the min. number of coins. Solutions are for GENERAL n. Let N = set of all mints, 1 to n. Card(N) = n. Let P = set of all bogus mints. Let Card(P) = p. Weighing I: Weigh n coins, 1 from each mint. Since each "good" coins weighs one ounce, let delta1 be the error in weighing. Since all bogus coins are identical, let delta1 be abs(error). If x is the weight by which one bogus coin differs from a good coin, delta1 = p * x. Weighing II: The coins to be weighed are composed thusly. Let a1 be the number of coins from mint 1, a2 # from mint2 .. and an from mint n. All ai's are distinct integers. Let A = Set of all ai's. Let delta2 = (abs.) error in weighing 2 = x * k where k is the number of coins that are bogus in weighing two. Or more formally k = sigma(ai) (over all i in P) Assuming p is not zero (from Weighing I - in that case go back and get beheaded for giving the king BAAAAAD advice), Let ratio = delta1/delta2 = p/k. Let IR = delta2/delta1 = k/p = inverse-ratio (for later proof). Let S(i) be the bag of all numbers generated by summing i distinct elements from A. Clearly there will be nCi (that n comb. i) elements in S(i). [A bag is a set that can have the same element occur more than once.] So S(1) = A and S(n) will have one element that is the sum of all the elements of A. Let R(i) = {x : For-all y in S(i), x = i/y} expressed as p/q (no common factors). (R is a bag too). Let R-A = Bag-Union(R(i) for 1>= i >=n). (can include same element twice) Choose A, such that all elements of R-A are DISTINCT, i.e. Bag(R-A) = Set(R-A). Let the sequence a1, a2, .. an, be an L-sequence if the above property is true. Or more simply, A is in L. ********************************************************************** CONJECTURE: The bogus mint problem is solved in two weighings if A is in L. Sketchy proof: R(1) = all possible ratios (= delta1/delta2) when p=1. R(i) = all possible ratio's when p=i. Since all possible combinations of bogus mints are reflected in R, just match the actual ratio with the generated table for n. ************************************************************************ A brief example. Say n=3. Skip to next line if you want. Let A=(2,3,7). p=1 possible ratios = 1/2 1/3 1/7 p=2 possible ratios = 2/5 2/9 1/5(2/10) p=3 possible ratios = 1/4(3/12) (lots of blood in Scandalvania). As all outcomes are distinct, and the actual ratio MUST be one of these, match it to the answer, and start sharpening the axe. Note that the minimum for n=3 is A=(0,1,3) possible ratios are p=1 infinity (delta2=0),1,1/3 p=2 2/1,2/3,1/2 p=3 3/4 ************************************************************************ All those with the determination to get this far are saying OK, OK how do we get A. I propose a solution that will generate A, to give you the answer in two weighings, but will not give you the optimal number of coins. Let a1=0 For i>=2 >=n ai = i*(a1 + a2 + ... + ai-1) + 1 ***************************************** * i-1 * * ai = i* [Sigma(aj)] + 1 * ****Generator function G***** * j=1 * ***************************************** If A is L, all RATIO's are unique. Also all inverse-ratio's (1/ratio) are unique. I will prove that all inverse-ratio's (or IR's) are unique. Let A(k), be the series generated by the first k elements from eqn. G.(above) ************************************************************************ PROOF BY INDUCTION. A(1) = {0} is in L. A(2) = {0,1} is in L. ASSUME A(k) = {0,1, ..., ak} is in L. T.P.T. A(k+1) = {0,1, ..., ak, D) is in L where D is generated from G. We know that all IR's(inverse ratio's) from A(k) are distinct. Let K = set of all IR's of A(k). Since A(k+1) contains A(k), all IR's of A(k) will also be IR's of A(K+1). So for all P, such that (k+1) is not in P, we get a distinct IR. So consider cases when (k+1) is in P. p=1 (i.e. (k+1) = only bogus mint), IR = D ______________________________________________________________________ CONJECTURE: Highest IR for A(k) = max(K) = ak Proof: Since max[A(k)] = ak, for p'= 1, max IR = ak/1 = ak for p'= 2, max IR (max sum of 2 ai's)/2 = (ak + ak-1)/2 < ak (as ak>ak-1). for p'= i max IR sum of largest i elements of A(k) -------------------------------- i < i * ak/i = ak. So max. IR for A(k) is ak. ______________________________________________________________________ D > ak So for p=1 IR is distinct. Let Xim be the IR formed by choosing i elements from A(k+1). Note: We are choosing D and (i-1) elements from A(k). m is just an index to denote each distinct combination of (i-1) elemnts of A(i). ______________________________________________________________________ CONJECTURE : For p=j, all new IR's Xjm are limited to the range D/(j-1) > Xjm > D/j. Proof: Xjm = (D + {j-1 elements of A(k)})/j Clearly Xjm > D/j. To show: max[Xjm] < D/(j-1) Note: a1 + a2 .. + ak < D/(k+1) max[Xjm] = (D + ak + ak-1 + ... + a(k-j+1))/j < (D + D/(k+1))/j = D (k+2)/(k+1)j = [D/(j-1)] * alpha. alpha = (j-1)/(j) * (k+2)/(k+1) Since j <= k, (j-1)/j <= (k-1)/k < (k+1)/(k+2) IMPLIES alpha < 1. Conjecture proved. ______________________________________________________________________ CONJECTURE : For a given p, all newly generated IR's are distinct. Proof by contradiction: Assume this is not so. Implies (D + (p-1) elements of A(k))/p = (D + some other (p-1) elements of A(k))/p Implies SUM[(p-1) elements of A(k)] = SUM[ some other (p-1) elements of A(k)] Implies SUM[(p-1) elements of A(k)]/(p-1) = SUM[some other (p-1) elements]/(p-1) Implies A(k) is NOT in L. Contra. Hence conjecture. ______________________________________________________________________ CONJECTURE: A(k+1) is in L. Since all newly generated IR's are distinct from each other, and all newly generated IR's are greater than previous IR's, A(k+1) is in L. ==> logic/zoo.p <== I took some nephews and nieces to the Zoo, and we halted at a cage marked Tovus Slithius, male and female. Beregovus Mimsius, male and female. Rathus Momus, male and female. Jabberwockius Vulgaris, male and female. The eight animals were asleep in a row, and the children began to guess which was which. "That one at the end is Mr Tove." "No, no! It's Mrs Jabberwock," and so on. I suggested that they should each write down the names in order from left to right, and offered a prize to the one who got most names right. As the four species were easily distinguished, no mistake would arise in pairing the animals; naturally a child who identified one animal as Mr Tove identified the other animal of the same species as Mrs Tove. The keeper, who consented to judge the lists, scrutinised them carefully. "Here's a queer thing. I take two of the lists, say, John's and Mary's. The animal which John supposes to be the animal which Mary supposes to be Mr Tove is the animal which Mary supposes to be the animal which John supposes to be Mrs Tove. It is just the same for every pair of lists, and for all four species. "Curiouser and curiouser! Each boy supposes Mr Tove to be the animal which he supposes to be Mr Tove; but each girl supposes Mr Tove to be the animal which she supposes to be Mrs Tove. And similarly for the oth- er animals. I mean, for instance, that the animal Mary calls Mr Tove is really Mrs Rathe, but the animal she calls Mrs Rathe is really Mrs Tove." "It seems a little involved," I said, "but I suppose it is a remarkable coincidence." "Very remarkable," replied Mr Dodgson (whom I had supposed to be the keeper) "and it could not have happened if you had brought any more children." How many nephews and nieces were there? Was the winner a boy or a girl? And how many names did the winner get right? [by Sir Arthur Eddington] ==> logic/zoo.s <== Given that there is at least one boy and one girl (John and Mary are mentioned) then the answer is that there were 3 nephews and 2 nieces, the winner was a boy who got 4 right. Number the animals 1 through 8, such that the females are even and the males are odd, with members of the same species consecutive; i.e. 1 is Mr. Tove, 2 Mrs. Tove, etc. Then each childs guesses can be represented by a permutation. I use the standard notation of a permutation as a set of orbits. For example: (1 3 5)(6 8) means 1 -> 3, 3 -> 5, 5 -> 1, 6 -> 8, 8 -> 6 and 2,4,7 are unchanged. [1] Let P be any childs guesses. Then P(mate(i)) = mate(P(i)). [2] If Q is another childs guesses, then [P,Q] = T, where [P,Q] is the commutator of P and Q (P composed with Q composed with P inverse composed with Q inverse) and T is the special permutation (1 2) (3 4) (5 6) (7 8) that just swaps each animal with its spouse. [3] If P represents a boy, then P*P = I (I use * for composition, and I for the identity permutation: (1)(2)(3)(4)(5)(6)(7)(8) [4] If P represents a girl, then P*P = T. [1] and [4] together mean that all girl's guesses must be of the form: (A B C D) (E F G H) where A and C are mates, as are B & D, E & F G & H. So without loss of generality let Mary = (1 3 2 4) (5 7 6 8) Without to much effort we see that the only possibilities for other girls "compatible" with Mary (I use compatible to mean the relation expressed in [2]) are: g1: (1 5 2 6) (3 8 4 7) g2: (1 6 2 5) (3 7 4 8) g3: (1 7 2 8) (3 5 4 6) g4: (1 8 2 7) (3 6 4 5) Note that g1 is incompatible with g2 and g3 is incompatible with g4. Thus no 4 of Mary and g1-4 are mutually compatible. Thus there are at most three girls: Mary, g1 and g3 (without loss of generality) By [1] and [3], each boy must be represented as a product of transpostions and/or singletons: e.g. (1 3) (2 4) (5) (6) (7) (8) or (1) (2) (3 4) (5 8) (6 7). Let J represent John's guesses and consider J(1). If J(1) = 1, then J(2) = 2 (by [1]) using [2] and Mary J(3) = 4, J(4) = 3, and g1 & J => J(5) = 6, J(6) = 5, & g3 & J => J(8) = 7 J(7) = 8 i.e. J = (1)(2)(3 4)(5 6)(7 8). But the [J,Mary] <> T. In fact, we can see that J must have no fixed points, J(i) <> i for all i, since there is nothing special about i = 1. If J(1) = 2, then we get from Mary that J(3) = 3. contradiction. If J(1) = 3, then J(2) = 4, J(3) = 1, J(4) = 2 (from Mary) => J(5) = 7, J(6) = 8, J(7) = 5, J(8) = 6 => J = (1 3)(2 4)(5 7)(6 8) (from g1) But then J is incompatible with g3. A similar analysis shows that J(1) cannot be 4,5,6,7 or 8; i.e. no J can be compatible with all three girls. So without loss of generality, throw away g3. We have Mary = (1 3 2 4) (5 7 6 8) g1 = (1 5 2 6) (3 8 4 7) The following are the only possible boy guesses which are compatible with both of these: B1: (1)(2)(3 4)(5 6)(7)(8) B2: (1 2)(3)(4)(5)(6)(7 8) B3: (1 3)(2 4)(5 7)(6 8) B4: (1 4)(2 3)(5 8)(6 7) B5: (1 5)(2 6)(3 8)(4 7) B6: (1 6)(2 5)(3 7)(4 8) Note that B1 & B2 are incombatible, as are B3 & B4, B5 & B6, so at most three of them are mutually compatible. In fact, Mary, g1, B1, B3 and B5 are all mutually compatible (as are all the other possibilities you can get by choosing either B1 or B2, B3 or B4, B5 or B6. So if there are 2 girls there can be 3 boys, but no more, and we have already eliminated the case of 3 girls and 1 boy. The only other possibility to consider is whether there can be 4 or more boys and 1 girl. Suppose there are Mary and 4 boys. Each boy must map 1 to a different digit or they would not be mutually compatible. For example if b1 and b2 both map 1 to 3, then they both map 3 to 1 (since a boy's map consists of transpositions), so both b1*b2 and b2*b1 map 1 to 1. Furthermore, b1 and b2 cannot map 1 onto spouses. For example, if b1(1) = a and b is the spouse of a, then b1(2) = b. If b2(1) = b, then b2(2) = a. Then b1*b2(1) = b1(b) = 2 and b2*b1(1) = b2(a) = 2 (again using the fact that boys are all transpostions). Thus the four boys must be: B1: (1)(2)... or (1 2).... B2: (1 3)... or (1 4) ... B3: (1 5) ... or (1 6) ... B4: (1 7) ... or (1 8) ... Consider B4. The only permutation of the form (1 7)... which is compatible with Mary ( (1 3 2 4) (5 7 6 8) ) is: (1 7)(2 8)(3 5)(4 6) The only (1 8)... possibility is: (1 8)(2 7)(3 6)(4 5) Suppose B4 = (1 7)(2 8)(3 5)(4 6) If B3 starts (1 5), it must be (1 5)(2 6)(3 8)(4 7) to be compatible with B4. This is compatible with Mary also. Assuming this and B2 starts with (1 3) we get B2 = (1 3)(2 4)(5 8)(6 7) in order to be compatible with B4. But then B2*B3 and B3*B2 moth map 1 to 8. I.e. no B2 is mutually compatible with B3 & B4. Similarly if B2 starts with (1 4) it must be (1 4)(2 3)(5 7)(6 8) to work with B4, but this doesn't work with B3. Likewise B3 starting with (1 6) leads to no possible B2 and the identical reasoning eliminates B4 = (1 8)... So no B4 is possible! I.e at most 3 boys are mutually compatiblw with Mary, so 2 girls & 3 boys is optimal. Thus: Mary = (1 3 2 4) (5 7 6 8) Sue = (1 5 2 6) (3 8 4 7) John = (1)(2)(3 4)(5 6)(7)(8) Bob = (1 3)(2 4)(5 7)(6 8) Jim = (1 5)(2 6)(3 8)(4 7) is one optimal solution, with the winner being John (4 right: 1 2 7 & 8) ==> physics/balloon.p <== A helium-filled balloon is tied to the floor of a car that makes a sharp right turn. Does the balloon tilt while the turn is made? If so, which way? The windows are closed so there is no connection with the outside air. ==> physics/balloon.s <== Because of buoyancy, the helium balloon on the string will want to move in the direction opposite the effective gravitational field existing in the car. Thus, when the car turns the corner, the balloon will deflect towards the inside of the turn. ==> physics/bicycle.p <== A boy, a girl and a dog go for a 10 mile walk. The boy and girl can walk 2 mph and the dog can trot at 4 mph. They also have bicycle which only one of them can use at a time. When riding, the boy and girl can travel at 12 mph while the dog can peddle at 16 mph. What is the shortest time in which all three can complete the trip? ==> physics/bicycle.s <== First note that there's no apparent way to benefit from letting either the boy or girl ride the bike longer than the other. Any solution which gets the boy there faster, must involve him using the bike (forward) more; similarly for the girl. Thus the bike must go backwards more for it to remain within the 10-mile route. Thus the dog won't make it there in time. So the solution assumes they ride the bike for the same amount of time. Also note that there's no apparent way to benefit from letting any of the three arrive at the finish ahead of the others. If they do, they can probably take time out to help the others. So the solution assumes they all finish at the same time. The boy starts off on the bike, and travels 5.4 miles. At this point, he drops the bike and completes the rest of the trip on foot. The dog eventually reaches the bike, and takes it *backward* .8 miles (so the girl gets to it sooner) and then returns to trotting. Finally, the girl makes it to the bike and rides it to the end. The answer is 2.75 hours. The puzzle is in Vasek Chvatal, Linear Programming, W. H. Freeman & Co. The generalized problem (n people, 1 bike, different walking and riding speeds) is known as "The Bicycle Problem". A couple references are Masuda, S. (1970). "The bicycle problem," University of California, Berkeley: Operations Research Center Technical Report ORC 70-35. Chvatal, V. (1983). "On the bicycle problem," Discrete Applied Mathematics 5: pp. 165 - 173. As for the linear program which gives the lower bound of 2.75 hours, let t[person, mode, direction] by the amount of time "person" (boy, girl or dog) is travelling by "mode" (walk or bike) in "direction" (forward or backwards). Define Time[person] to be the total time spent by person doing each of these four activities. The objective is to minimize the maximum of T[person], for person = boy, girl, dog, e.g. minimize T subject to T >= T[boy], T >= T[girl], T >= T[dog]. Now just think of all the other linear constraints on the variables t[x,y,z], such as everyone has to travel 10 miles, etc. In all, there are 8 contraints in 18 variables (including slack variables). Solving this program yields the lower bound. ==> physics/boy.girl.dog.p <== A boy, a girl and a dog are standing together on a long, straight road. Simulataneously, they all start walking in the same direction: The boy at 4 mph, the girl at 3 mph, and the dog trots back and forth between them at 10 mph. Assume all reversals of direction instantaneous. In one hour, where is the dog and in which direction is he facing? ==> physics/boy.girl.dog.s <== The dog's position and direction are indeterminate, other than that the dog must be between the boy and girl (endpoints included). To see this, simply time reverse the problem. No matter where the dog starts out, the three of them wind up together in one hour. This argument is not quite adequate. It is possible to construct problems where the orientation changes an infinite number of times initially, but for which there can be a definite result. This would be the case if the positions at time t are uniformly continuous in the positions at time s, s small. But suppose that at time a the dog is with the girl. Then the boy is at 4a, and the time it takes the dog to reach the boy is a/6, because the relative speed is 6 mph. So the time b at which the dog reaches the boy is proportional to a. A similar argument shows that the time the dog next reaches the girl is b + b/13, and is hence proportional to b. This makes the position of the dog at time (t > a) a periodic function of the logarithm of a, and thus does not approach a limit as a -> 0. ==> physics/brick.p <== What is the maximum overhang you can create with an infinite supply of bricks? ==> physics/brick.s <== You can create an infinite overhang. Let us reverse the problem: how far can brick 1 be from brick 0? Let us assume that the brick is of length 1. To determine the place of the center of mass a(n): a(1)=1/2 a(n)=1/n[(n-1)*a(n-1)+[a(n-1)+1/2]]=a(n-1)+1/(2n) Thus n 1 n 1 a(n)=Sum -- = 1/2 Sum - = 1/2 H(n) m=1 2m m=1 m Needless to say the limit for n->oo of half the Harmonic series is oo. ==> physics/cannonball.p <== A person in a boat drops a cannonball overboard; does the water level change? ==> physics/cannonball.s <== The cannonball in the boat displaces an amount of water equal to the MASS of the cannonball. The cannonball in the water displaces an amount of water equal to the VOLUME of the cannonball. Water is unable to support the level of salinity it would take to make it as dense as a cannonball, so the first amount is definitely more than the second amount, and the water level drops. ==> physics/dog.p <== A body of soldiers form a 50m-by-50m square ABCD on the parade ground. In a unit of time, they march forward 50m in formation to take up the position DCEF. The army's mascot, a small dog, is standing next to its handler at location A. When the B----C----E soldiers start marching, the dog | | | forward--> begins to run around the moving A----D----F body in a clockwise direction, keeping as close to it as possible. When one unit of time has elapsed, the dog has made one complete circuit and has got back to its handler, who is now at location D. (We can assume the dog runs at a constant speed and does not delay when turning the corners.) How far does the dog travel? ==> physics/dog.s <== Let L be the side of the square, 50m, and let D be the distance the dog travels. Let v1 be the soldiers' marching speed and v2 be the speed of the dog. Then v1 = L / (1 time unit) and v2 = v1*D/L. Let t1, t2, t3, t4 be the time the dog takes to traverse each side of the square, in order. Find t1 through t4 in terms of L and D and solve t1+t2+t3+t4 = 1 time unit. While the dog runs along the back edge of the square in time t1, the soldiers advance a distance d=t1*v1, so the dog has to cover a distance sqrt(L^2 + (t1*v1)^2), which takes a time t1=sqrt(L^2 + (t1*v1)^2)/v2. Solving for t1 gives t1=L/sqrt(v2^2 - v1^2). The rest of the times are t2 = L/(v2-v1), t3 = t1, and t4 = L/(v2+v1). In t1+t2+t3+t4, eliminate v2 by using v2=v1*D/L and eliminate v1 by using v1=L/(1 time unit), obtaining 2 L (D + sqrt(D^2-L^2)) / (D^2 - L^2) = 1 which can be turned into D^4 - 4LD^3 - 2L^2D^2 + 4L^3D + 5L^4 = 0 which has a root D = 4.18113L = 209.056m. ==> physics/magnets.p <== You have two bars of iron. One is magnetic, the other is not. Without using any other instrument (thread, filings, other magnets, etc.), find out which is which. ==> physics/magnets.s <== Take the two bars, and put them together like a T, so that one bisects the other. ___________________ bar A ---> |___________________| | | | | | | | | bar B ------------> | | | | | | |_| If they stick together, then bar B is the magnet. If they don't, bar A is the magnet. (reasoning follows) Bar magnets are "dead" in their centers (ie there is no magnetic force, since the two poles cance out). So, if bar A is the magnet, then bar B won't stick to its center. However, bar magnets are quite "alive" at their edges (ie the magnetic force is concentrated). So, if bar B is the magnet, then bar A will stick nicely to its end. ==> physics/milk.and.coffee.p <== You are just served a hot cup of coffee and want it to be as hot as possible when you drink it some number of minutes later. Do you add milk when you get the cup or just before you drink it? ==> physics/milk.and.coffee.s <== Normalize your temperature scale so that 0 degrees = room temperature. Assume that the coffee cools at a rate proportional to the difference in temperature, and that the amount of milk is sufficiently small that the constant of proportinality is not changed when you add the milk. An early calculus homework problem is to compute that the temperature of the coffee decays exponentially with time, T(t) = exp(-ct) T0, where T0 = temperature at t=0. Let l = exp(-ct), where t is the duration of the experiment. Assume that the difference in specific heats of coffee and milk are negligible, so that if you add milk at temperature M to coffee at temperature C, you get a mix of temperature aM+bC, where a and b are constants between 0 and 1, with a+b=1. (Namely, a = the fraction of final volume that is milk, and b = fraction that is coffee.) If we let C denote the original coffee temperature and M the milk temperature, we see that Add milk later: aM + blC Add milk now: l(aM+bC) = laM+blC The difference is d=(1-l)aM. Since l<1 and a>0, we need to worry about whether M is positive or not. M>0: Warm milk. So d>0, and adding milk later is better. M=0: Room temp. So d=0, and it doesn't matter. M<0: Cold milk. So d<0, and adding milk now is better. Of course, if you wanted to be intuitive, the answer is obvious if you assume the coffee is already at room temperature and the milk is either scalding hot or subfreezing cold. Moral of the story: Always think of extreme cases when doing these puzzles. They are usually the key. Oh, by the way, if we are allowed to let the milk stand at room temperature, then let r = the corresponding exponential decay constant for your milk container. Add acclimated milk later: arM + blC We now have lots of cases, depending on whether r<l: The milk pot is larger than your coffee cup. (E.g, it really is a pot.) r>l: The milk pot is smaller than your coffee cup. (E.g., it's one of those tiny single-serving things.) M>0: The milk is warm. M<0: The milk is cold. Leaving out the analysis, I compute that you should... Add warm milk in large pots LATER. Add warm milk in small pots NOW. Add cold milk in large pots NOW. Add cold milk in small pots LATER. Of course, observe that the above summary holds for the case where the milk pot is allowed to acclimate; just treat the pot as of infinite size. ==> physics/mirror.p <== Why does a mirror appear to invert the left-right directions, but not up-down? ==> physics/mirror.s <== Mirrors invert front to back, not left to right. The popular misconception of the inversion is caused by the fact that a person when looking at another person expects him/her to face her/him, so with the left-hand side to the right. When facing oneself (in the mirror) one sees an 'uninverted' person. See Martin Gardner, ``Hexaflexagons and other mathematical diversions,'' University of Chicago Press 1988, Chapter 16. A letter by R.D. Tschigi and J.L. Taylor published in this book states that the fundamental reason is: ``Human beings are superficially and grossly bilaterally symmetrical, but subjectively and behaviorally they are relatively asymmetrical. The very fact that we can distinguish our right from our left side implies an asymettry of the perceiving system, as noted by Ernst Mach in 1900. We are thus, to a certain extent, an asymmetrical mind dwelling in a bilaterally symmetrical body, at least with respect to a casual visual inspection of our external form.'' Martin Gardner has also written the book ``The Amidextrous Universe.'' ==> physics/monkey.p <== Hanging over a pulley, there is a rope, with a weight at one end. At the other end hangs a monkey of equal weight. The rope weighs 4 ounces per foot. The combined ages of the monkey and it's mother is 4 years. The weight of the monkey is as many pounds as the mother is years old. The mother is twice as old as the monkey was when the mother was half as old as the monkey will be when the monkey is 3 times as old as the mother was when she was 3 times as old as the monkey. The weight of the rope and the weight is one-half as much again as the difference between the weight of the weight and the weight of the weight plus the weight of the monkey. How long is the rope? ==> physics/monkey.s <== The most difficult thing about this puzzle, as you probably expected, is translating all the convoluted problem statements into equations... the solution is pretty trivial after that. So... Let: m represent monkey M represent mother of monkey w represent weight r represent rope W[x] = present weight of x (x is m, M, w, or r) A[x,t] = age of x at time t (x is M or M, t is one of T1 thru T4) T1 = time at which mother is 3 times as old as monkey T2 = time at which monkey is 3 times as old as mother at T1 T3 = time at which mother is half as old as monkey at T2 T4 = present time For the ages, we have: A[M,T1] = 3*A[m,T1] A[m,T2] = 3*A[M,T1] = 9*A[m,T1] A[M,T3] = A[m,T2]/2 = 9*A[m,T1]/2 A[m,T3] = A[m,T1] + (T3-T1) = A[m,T1] + (A[M,T3]-A[M,T1]) = A[m,T1] + (9*A[M,T1]/2 - 3*A[m,T1]) = 5*A[m,T1]/2 A[M,T4] = 2*A[m,T3] = 5*A[m,T1] A[m,T4] = A[m,T1] + (T4-T1) = A[m,T1] + (A[M,T4]-A[M,T1]) = A[m,T1] + (5*A[m,T1] - 3*A[m,T1]) = 3*A[m,T1] The present ages of monkey and mother sum to 4, so we have A[m,T4] + A[M,T4] = 4 3*A[m,T1] + 5*A[m,T1] = 4 8*A[m,T1] = 4 A[m,T1] = 1/2 Thus: A[M,T4] = 5/2 A[m,T4] = 3/2 Now for the weights, translating everything to ounces: Monkey's weight in lbs = mother's age in years, so: W[m] = 16*5/2 = 40 Weight and monkey are same weight, so: W[w] = W[m] = 40 The last paragraph in the problem translates into: W[r]+W[w] = (3/2)*((W[w]+W[m])-W[w]) W[r]+ 40 = (3/2)*(( 40 + 40 )- 40 ) W[r]+ 40 = 60 W[r] = 20 The rope weighs 4 ounces per foot, so its length is 5 feet. ==> physics/particle.p <== What is the longest time that a particle can take in travelling between two points if it never increases its acceleration along the way and reaches the second point with speed V? ==> physics/particle.s <== Assumptions: 1. x(0) = 0; x(T) = X 2. v(0) = 0; v(T) = V 3. d(a)/dt <= 0 Solution: a(t) = constant = A = V^2/2X which implies T = 2X/V. Proof: Consider assumptions as they apply to f(t) = A * t - v(t): 1. integral from 0 to T of f = 0 2. f(0) = f(T) = 0 3. d^2(f)/dt^2 <= 0 From the mean value theorem, f(t) = 0. QED. ==> physics/pole.in.barn.p <== Accelerate a pole of length l to a constant speed of 90% of the speed of light (.9c). Move this pole towards an open barn of length .9l (90% the length of the pole). Then, as soon as the pole is fully inside the barn, close the door. What do you see and what actually happens? ==> physics/pole.in.barn.s <== What the observer sees depends upon where the observer is, due to the finite speed of light. For definiteness, assume the forward end of the pole is marked "A" and the after end is marked "B". Let's also assume there is a light source inside the barn, and that the pole stops moving as soon as end "B" is inside the barn. An observer inside the barn next to the door will see the following sequence of events: 1. End "A" enters the barn and continues toward the back. 2. End "B" enters the barn and stops in front of the observer. 3. The door closes. 4. End "A" continues moving and penetrates the barn at the far end. 5. End "A" stops outside the barn. An observer at the other end of the barn will see: 1. End "A" enters the barn. 2. End "A" passes the observer and penetrates the back of the barn. 3. If the pole has markings on it, the observer will notice the part nearest him has stopped moving. However, both ends are still moving. 4. End "A" stops moving outside the barn. 5. End "B" continues moving until it enters the barn and then stops. 6. The door closes. After the observers have subtracted out the effects of the finite speed of light on what they see, both observers will agree on what happened: The pole entered the barn; the door closed so that the pole was completely contained within the barn; as the pole was being stopped it elongated and penetrated the back wall of the barn. Things are different if you are riding along with the pole. The pole is never inside the barn since it won't fit. End A of the pole penetrates the rear wall of the barn before the door is closed. If the wall of the barn is impenetrable, in all the above scenarios insert the wording "End A of the pole explodes" for "End A penetrates the barn." ==> physics/resistors.p <== What are the resistances between lattices of resistors in the shape of a: 1. Cube 2. Platonic solid 3. Hypercube 4. Plane sheet 5. Continuous sheet ==> physics/resistors.s <== 1. Cube The key idea is to observe that if you can show that two points in a circuit must be at the same potential, then you can connect them, and no current will flow through the connection and the overall properties of the circuit remain unchanged. In particular, for the cube, there are three resistors leaving the two "connection corners". Since the cube is completely symmetrical with respect to the three resistors, the far sides of the resistors may be connected together. And so we end up with: |---WWWWWW---| |---WWWWWW---| | | | | *--+---WWWWWW---+----+---WWWWWW---+---* | | | | |---WWWWWW---| |---WWWWWW---| 2. Platonic Solids Same idea for 8 12 and 20, since you use the symmetry to identify equi-potential points. The tetrahedron is hair more subtle: *---|---WWWWWW---|---* |\ /| W W W W W W W W W W W W | \ / | \ || | \ | / \ W / \ W / <------- \ W / \|/ + By symmetry, the endpoints of the marked resistor are equi-potential. Hence they can be connected together, and so it becomes a simple: *---+---WWWWW---+----* | | +-WWW WWW-+ | |-| | |-WWW WWW-| 3. Hypercube Think of injecting a constant current I into the start vertex. It splits (by symmetry) into n equal currents in the n arms; the current of I/n then splits into I/n(n-1), which then splits into I/[n(n-1)(n-1)] and so on till the halfway point, when these currents start adding up. What is the voltage difference between the antipodal points? V = I x R; add up the voltages along any of the paths: n even: (n-2)/2 V = 2{I/n + I/(n(n-1)) + I/(n(n-1)(n-1)) + ... + I/(n(n-1) )} n odd: (n-3)/2 V = 2{I/n + I/(n(n-1)) + I/(n(n-1)(n-1)) + ... + I/(n(n-1) )} (n-1)/2 + I/(n(n-1) ) And R = V/I i.e. replace the Is in the above expression by 1s. For the 3-cube: R = 2{1/3} + 1/(3x2) = 5/6 ohm For the 4-cube: R = 2{1/4 + 1/(4x3)} = 2/3 ohm This formula yields the resistance from root to root of two (n-1)-ary trees of height n/2 with their end nodes identified (-when n is even; something similar when n is odd). Coincidentally, the 4-cube is such an animal and thus the answer 2/3 ohms is correct in that case. However, it does not provide the solution for n >= 5, as the hypercube does not have quite as many edges as were counted in the formula above. 4. The Infinite Plane For an infinite lattice: First inject a constant current I at a point; figure out the current flows (with heavy use of symmetry). Remove that current. Draw out a current I from the other point of interest (or inject a negative current) and figure out the flows (identical to earlier case, but displaced and in the other direction). By the principle of superposition, if you inject a current I into point a and take out a current I at point b at the same time, the currents in the paths are simply the sum of the currents obtained in the earlier two simpler cases. As in the n-cube, find the voltage between the points of interest, divide by I and voila'! As an illustration, in the adjacent points case: we have a current of I/4 in each of the four resistors: ^ | | v <--o--> -->o<-- | ^ v | (inject) (take out) And adding the currents, we have I/2 in the resistor connecting the two points. Therefore V=(1 ohm) x I/2 and effective resistance between the points = 1/2 ohm. You can (and showed how to) use symmetry to obtain the equivalent resistance of 1/2 between two adjacent nodes; but I doubt that symmetry alone will give you even the equivalent resistance of 2/pi between two diagonally adjacent nodes. [More generally, the equivalent resistance between two nodes k diagonal units apart is (2/pi)(1+1/3+1/5+...+1/(2k-1)); that, plus symmetry and the known equivalent resistance between two adjacent nodes, is sufficient to derive all equivalent resistances in the lattice. 5. Continuous sheet Doesn't the resistance diverge in that case? The problem is that you can't inject current at a point. cf. "Random Walks and Electric Networks", by Doyle and Snell, published by the Mathematical Association of America. ==> physics/sail.p <== A sailor is in a sailboat on a river. The water (current) is flowing downriver at a velocity of 3 knots with respect to the land. The wind (air velocity) is zero, with respect to the land. The sailor wants to proceed downriver as quickly as possible, maximizing his downstream speed with respect to the land. Should he raise the sail, or not? ==> physics/sail.s <== Depends on the sail. If the boat is square-rigged, then not, since raising the sail will simply increase the air resistance. If the sailor has a fore-and-aft rig, then he should, since he can then tack into the wind. (Imagine the boat in still water with a 3-knot head wind). ==> physics/skid.p <== What is the fastest way to make a 90 degree turn on a slippery road? ==> physics/skid.s <== For higher speeds (measured at a small distance from the point of initiation of a sharp turn) the fastest way round is to "outside loop" - that is, steer away from the curve, and do a kidding 270. This technique is taught in advanced driving schools. References: M. Freeman and P. Palffy, American Journal of Physics, vol 50, p. 1098, 1982. P. Palffy and Unruh, American Journal of Physics, vol 49, p. 685, 1981. ==> physics/spheres.p <== Two spheres are the same size and weight, but one is hollow. They are made of uniform material, though of course not the same material. Without a minimum of apparatus, how can I tell which is hollow? ==> physics/spheres.s <== Since the balls have equal diameter and equal mass, their volume and density are also equal. However, the mass distribution is not equal, so they will have different moments of inertia - the hollow sphere has its mass concentrated at the outer edge, so its moment of inertia will be greater than the solid sphere. Applying a known torque and observing which sphere has the largest angular acceleration will determine which is which. An easy way to do this is to "race" the spheres down an inclined plane with enough friction to prevent the spheres from sliding. Then, by conservation of energy: mgh = 1/2 mv^2 + 1/2 Iw^2 Since the spheres are rolling without sliding, there is a relationship between velocity and angular velocity: w = v / r so mgh = 1/2 mv^2 + 1/2 I (v^2 / r^2) = 1/2 (m + I/r^2) v^2 and v^2 = 2mgh / (m + I / r^2) From this we can see that the sphere with larger moment of inertia (I) will have a smaller velocity when rolled from the same height, if mass and radius are equal with the other sphere. Thus the solid sphere will roll faster. ==> physics/wind.p <== Is a round-trip by airplane longer or shorter if there is wind blowing? ==> physics/wind.s <== It will take longer, by the ratio (s^2)/(s^2 - w^2) where s is the plane's speed, and w is the wind speed. The stronger the wind the longer it will take, up until the wind speed equals the planes speed, at which point the plane will never finish the trip. Math: s = plane's speed w = wind speed d = distance in one direction d / (s + w) = time to complete leg flying with the wind d / (s - w) = time to complete leg flying against the wind d / (s + w) + d / (s - w) = round trip time d / (s + w) + d / (s - w) = ratio of flying with wind to ------------------------- flying with no wind (bottom of d / s + d / s equation is top with w = 0) this simplifies to s^2 / (s^2 - w^2). ==> probability/amoeba.p <== A jar begins with one amoeba. Every minute, every amoeba turns into 0, 1, 2, or 3 amoebae with probability 25% for each case ( dies, does nothing, splits into 2, or splits into 3). What is the probability that the amoeba population eventually dies out? ==> probability/amoeba.s <== If p is the probability that a single amoeba's descendants will die out eventually, the probability that N amoebas' descendents will all die out eventually must be p^N, since each amoeba is independent of every other amoeba. Also, the probability that a single amoeba's descendants will die out must be independent of time when averaged over all the possibilities. At t=0, the probability is p, at t=1 the probability is 0.25(p^0+p^1+p^2+p^3), and these probabilities must be equal. Extinction probability p is a root of f(p)=p. In this case, p = sqrt(2)-1. The generating function for the sequence P(n,i), which gives the probability of i amoebas after n minutes, is f^n(x), where f^n(x) == f^(n-1) ( f(x) ), f^0(x) == x . That is, f^n is the nth composition of f with itself. Then f^n(0) gives the probability of 0 amoebas after n minutes, since f^n(0) = P(n,0). We then note that: f^(n+1)(x) = ( 1 + f^n(x) + (f^n(x))^2 + (f^n(x))^3 )/4 so that if f^(n+1)(0) -> f^n(0) we can solve the equation. The generating function also gives an expression for the expectation value of the number of amoebas after n minutes. This is d/dx(f^n(x)) evaluated at x=1. Using the chain rule we get f'(f^(n-1)(x))*d/dx(f^(n-1)(x)) and since f'(1) = 1.5 and f(1) = 1, we see that the result is just 1.5^n, as might be expected. ==> probability/apriori.p <== An urn contains one hundred white and black balls. You sample one hundred balls with replacement and they are all white. What is the probability that all the balls are white? ==> probability/apriori.s <== This question cannot be answered with the information given. In general, the following formula gives the conditional probability that all the balls are white given you have sampled one hundred balls and they are all white: P(100 white | 100 white samples) = P(100 white samples | 100 white) * P(100 white) ----------------------------------------------------------- sum(i=0 to 100) P(100 white samples | i white) * P(i white) The probabilities P(i white) are needed to compute this formula. This does not seem helpful, since one of these (P(100 white)) is just what we are trying to compute. However, the following argument can be made: Before the experiment, all possible numbers of white balls from zero to one hundred are equally likely, so P(i white) = 1/101. Therefore, the odds that all 100 balls are white given 100 white samples is: P(100 white | 100 white samples) = 1 / ( sum(i=0 to 100) (i/100)^100 ) = 63.6% This argument is fallacious, however, since we cannot assume that the urn was prepared so that all possible numbers of white balls from zero to one hundred are equally likely. In general, we need to know the P(i white) in order to calculate the P(100 white | 100 white samples). Without this information, we cannot determine the answer. This leads to a general "problem": our judgments about the relative likelihood of things is based on past experience. Each experience allows us to adjust our likelihood judgment, based on prior probabilities. This is called Bayesian inference. However, if the prior probabilities are not known, then neither are the derived probabilities. But how are the prior probabilities determined? For example, if we are brains in the vat of a diabolical scientist, all of our prior experiences are illusions, and therefore all of our prior probabilities are wrong. All of our probability judgments indeed depend upon the assumption that we are not brains in a vat. If this assumption is wrong, all bets are off. ==> probability/cab.p <== A cab was involved in a hit and run accident at night. Two cab companies, the Green and the Blue, operate in the city. Here is some data: a) Although the two companies are equal in size, 85% of cab accidents in the city involve Green cabs and 15% involve Blue cabs. b) A witness identified the cab in this particular accident as Blue. The court tested the reliability of the witness under the same circumstances that existed on the night of the accident and concluded that the witness correctly identified each one of the two colors 80% of the time and failed 20% of the time. What is the probability that the cab involved in the accident was Blue rather than Green? If it looks like an obvious problem in statistics, then consider the following argument: The probability that the color of the cab was Blue is 80%! After all, the witness is correct 80% of the time, and this time he said it was Blue! What else need be considered? Nothing, right? If we look at Bayes theorem (pretty basic statistical theorem) we should get a much lower probability. But why should we consider statistical theorems when the problem appears so clear cut? Should we just accept the 80% figure as correct? ==> probability/cab.s <== The police tests don't apply directly, because according to the wording, the witness, given any mix of cabs, would get the right answer 80% of the time. Thus given a mix of 85% green and 15% blue cabs, he will say 20% of the green cabs and 80% of the blue cabs are blue. That's 20% of 85% plus 80% of 15%, or 17%+12% = 29% of all the cabs that the witness will say are blue. Of those, only 12/29 are actually blue. Thus P(cab is blue | witness claims blue) = 12/29. That's just a little over 40%. Think of it this way... suppose you had a robot watching parts on a conveyor belt to spot defective parts, and suppose the robot made a correct determination only 50% of the time (I know, you should probably get rid of the robot...). If one out of a billion parts are defective, then to a very good approximation you'd expect half your parts to be rejected by the robot. That's 500 million per billion. But you wouldn't expect more than one of those to be genuinely defective. So given the mix of parts, a lot more than 50% of the REJECTED parts will be rejected by mistake (even though 50% of ALL the parts are correctly identified, and in particular, 50% of the defective parts are rejected). When the biases get so enormous, things starts getting quite a bit more in line with intuition. For a related real-life example of probability in the courtroom see People v. Collins, 68 Cal 2d319 (1968). ==> probability/coincidence.p <== Name some amazing coincidences. ==> probability/coincidence.s <== The answer to the question, "Who wrote the Bible," is, of course, Shakespeare. The King James Version was published in 1611. Shakespeare was 46 years old then (he turned 47 later in the year). Look up Psalm 46. Count 46 words from the beginning of the Psalm. You will find the word "Shake." Count 46 words from the end of the Psalm. You will find the word "Spear." An obvious coded message. QED. How many inches in the pole-to-pole diameter of the Earth? The answer is almost exactly 500,000,000 inches. Proof that the inch was defined by spacemen. ==> probability/coupon.p <== There is a free gift in my breakfast cereal. The manufacturers say that the gift comes in four different colours, and encourage one to collect all four (& so eat lots of their cereal). Assuming there is an equal chance of getting any one of the colours, what is the expected number of packets I must plough through to get all four? Can you generalise to n colours and/or unequal probabilities?